{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 合并两个有序数组\n",
    "\n",
    "给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。\n",
    "\n",
    "说明:\n",
    "\n",
    "    初始化 nums1 和 nums2 的元素数量分别为 m 和 n。\n",
    "    你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。\n",
    "\n",
    "示例:\n",
    "\n",
    "```\n",
    "输入:\n",
    "nums1 = [1,2,3,0,0,0], m = 3\n",
    "nums2 = [2,5,6],       n = 3\n",
    "\n",
    "输出: [1,2,2,3,5,6]\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Trying:\n",
      "    Solution().merge([1,2,3,0,0,0], 3, [2,5,6], 3)\n",
      "Expecting:\n",
      "    [1, 2, 2, 3, 5, 6]\n",
      "ok\n",
      "2 items had no tests:\n",
      "    __main__.Solution\n",
      "    __main__.Solution.merge\n",
      "1 items passed all tests:\n",
      "   1 tests in __main__\n",
      "1 tests in 3 items.\n",
      "1 passed and 0 failed.\n",
      "Test passed.\n"
     ]
    }
   ],
   "source": [
    "\"\"\" 在 nums1 的地址空间合并 nums2 , 不用返回值。\n",
    "# Testcase:\n",
    "\n",
    ">>> Solution().merge([1,2,3,0,0,0], 3, [2,5,6], 3)\n",
    "[1, 2, 2, 3, 5, 6]\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def merge(self, nums1, m, nums2, n):\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums1 in-place instead.\n",
    "        使用 归并排序的 merge 过程，nums1 声明为 global ,或者使用 copy  无效；结果判断使用的引用地址\n",
    "        \"\"\"\n",
    "        i,j = 0, 0\n",
    "        temp = []\n",
    "        if m>1 and n<=0:\n",
    "            return nums1\n",
    "        elif m<=0 and n > 1:\n",
    "            for i in range(0,n):\n",
    "                nums1[i] = nums2[i]\n",
    "        else:\n",
    "            while i <= m and j < n:\n",
    "                if nums1[i] <= nums2[j]:\n",
    "                    if nums1[i] == 0 and i >= m:\n",
    "                        nums1[i] = nums2[j]\n",
    "                        j += 1\n",
    "                        m += 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    temp = nums1[i:m]\n",
    "                    nums1[i] = nums2[j]\n",
    "                    j += 1\n",
    "                    i += 1\n",
    "                    m += 1\n",
    "                    nums1[i:m] = temp\n",
    "            if j < n:\n",
    "                nums1.extend(nums2[j:n])\n",
    "        # 原题不要求返回值，为便于测试只打印\n",
    "        print(nums1)\n",
    "        \n",
    "if __name__ == \"__main__\":\n",
    "    import doctest\n",
    "    doctest.testmod(verbose=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 题解：\n",
    "对于有序列表的合并，最直接用归并排序的合并过程，但是该题要求在 nums1 地址空间合并，就需要考虑到 python 变量值引用的问题，也推测不希望有额外的空间；\n",
    "那么结合题意，可以选择插入排序，不同的是在替换元素的过程中 nums1 的长度 m 是要扩张的，占位符为\"0\"。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
